package 树;

import 动态数组.线性表.List;
import 动态链表.LinkedList;
import 集合.LinkedSet;
import 集合.TreeSet;
import 集合.接口.Map;
import 集合.接口.Set;

import java.util.Iterator;

public class HashTable<K extends Comparable<K>,V> implements Map<K,V> {

    private static final int[] capacity = {
            53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 768433, 1572869, 3145739, 6291469,
            12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741
    };

    private int capacityIndex = 0;
    //每个桶的上限和下限，大于上限就扩，小于下限就缩
    private int upperTol = 10;
    private int loWerTol = 3;
    private AVLTreeMap<K,V>[] hashTable;
    private int M; //哈希表的长度，桶的数量
    private int size; //元素的个数

    public HashTable(){
        M = capacity[capacityIndex];
        size = 0;
        hashTable = new AVLTreeMap[M];
        for (int i = 0; i < hashTable.length; i++) {
            hashTable[i] = new AVLTreeMap<>();
        }
    }

    private int hash(K key){
        //& 去负值
        return key.hashCode() & 0x7fffffff % M;
    }


    @Override
    public void put(K key, V value) {
        int index = hash(key);
        AVLTreeMap<K, V> map = hashTable[index];
        if (map.contains(key)){
            map.put(key,value);
        }else {
            map.put(key,value);
            size++;
            if (size >= upperTol * M && capacityIndex + 1 < capacity.length){
                //扩容
                resize(capacity[++capacityIndex]);
            }
        }

    }

    private void resize(int newM) {
        AVLTreeMap<K, V>[] newHashTable = new AVLTreeMap[newM];
        for (int i = 0; i < hashTable.length; i++) {
            newHashTable[i] = new AVLTreeMap<>();
        }
        int oldM = M;
        M = newM;
        for (int i = 0; i < oldM; i++) {
            AVLTreeMap<K, V> map = hashTable[i];
            for (K key : map.keySet()) {
                newHashTable[hash(key)].put(key,map.get(key));
            }
        }
    }

    @Override
    public V remove(K key) {
        int index =  hash(key);
        AVLTreeMap<K, V> map = hashTable[index];
        V ret = null;
        if (map.contains(key)){
            ret = map.remove(key);
            size--;
            if (size < loWerTol * M && capacityIndex - 1 > 0){
                resize(capacity[--capacityIndex]);
            }
        }
        return ret;
    }

    @Override
    public boolean contains(K key) {
        int index = hash(key);
        AVLTreeMap<K, V> map = hashTable[index];
        return map.contains(key);
    }

    @Override
    public V get(K key) {
        int index = hash(key);
        AVLTreeMap<K, V> map = hashTable[index];
        return map.get(key);
    }

    @Override
    public V set(K key, V value) {
        int index = hash(key);
        AVLTreeMap<K, V> map = hashTable[index];
        return map.set(key,value);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Set<K> keySet() {
        TreeSet<K> set = new TreeSet<>();
        for (int i = 0; i < M; i++) {
            AVLTreeMap<K, V> map = hashTable[i];
            for (K key : map.keySet()) {
                set.add(key);
            }
        }
        return set;
    }

    @Override
    public List<V> values() {
        LinkedList<V> list = new LinkedList<>();
        for (int i = 0; i < M; i++) {
            AVLTreeMap<K, V> map = hashTable[i];
            for (V value : map.values()) {
                list.add(value);
            }
        }
        return list;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        LinkedSet<Entry<K,V>> list = new LinkedSet<>();
        for (int i = 0; i < M; i++) {
            AVLTreeMap<K, V> map = hashTable[i];
            for (Entry<K, V> entry : map.entrySet()) {
                list.add(entry);
            }
        }
        return list;
    }

    @Override
    public Iterator<Entry<K, V>> iterator() {
        return null;
    }


    private class HashTableIterator implements Iterator<Entry>{

        private Set<Entry<K,V>> set;
        private LinkedList<Entry<K,V>> list;

        public HashTableIterator(){
            set = entrySet();
            list = new LinkedList<>();
            for (Entry<K, V> entry : set) {
                list.add(entry);
            }
        }

        @Override
        public boolean hasNext() {
            return !list.isEmpty();
        }

        @Override
        public Entry next() {
            return list.removeFirst();
        }
    }
}
